package com.atwy.sort;

/**
 * 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
 * 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
 * （如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
 * <p>
 * 1.从第一个元素开始，该元素可以认为已经被排序；
 * 2.取出下一个元素，在已经排序的元素序列中 从后向前 扫描；
 * 3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
 * 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
 * 5.将新元素插入到该位置后；
 * 6.重复步骤2~5。
 */
public class InsertionSort {

    public static void main(String[] args) {
        int[] array = {3, 65, 2, 34, 12, 5, 9, 12};
        sort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println();
        System.out.println("=============");

        int max = 80000;
        int arry[] = new int[max];
        for (int i = 0; i < max; i++) {
            arry[i] = (int)(Math.random()*8000000);
        }
        long start = System.currentTimeMillis();
        System.out.println("排序开始:"+start);
        sort(arry);
        long end = System.currentTimeMillis();
        System.out.println("排序结束:"+end);
        System.out.println("总耗时"+(end-start));
    }

    public static void sort(int[] array) {
        if (array.length < 2) {
            return;
        }
        int temp;
        int index;// 待插入的位置
        for (int i = 1; i < array.length; i++) {// 无序序列
            temp = array[i];
            index = i;
            for (int j = i - 1; j >= 0; j--) {// 有序序列
                // 从无序的序列中取一个数，与有序序列从后往前比较
                if (temp < array[j]) {
                    // j 与 j+1 换位置
                    array[j + 1] = array[j];
                    index = j;
                } else {
                    break;
                }
            }
            if (index != i) {
                array[index] = temp;
            }

        }

    }

    /**
     * 用 while处理内层循环
     *
     * @param array
     */
    public static void sort2(int[] array) {
        if (array.length < 2) {
            return;
        }
        int temp;
        int j;
        for (int i = 1; i < array.length; i++) {// 无序序列
            //记录要插入的数据
            temp = array[i];
            j = i;// [0,j-1]之间是有序序列
            while (j > 0 && array[j - 1] > temp) {
                //序列往后移，空出一个留给待插入的数据
                array[j] = array[j - 1];
                //j向前移动1，标记空出来位置是否进行插入
                j--;
            }
            if (j != i) {
                array[j] = temp;
            }
        }
    }



}
